import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
class InOrderThreadTreeNode {
    int val;
    InOrderThreadTreeNode left;
    InOrderThreadTreeNode right;
    int leftTag;
    int rightTag;
    public InOrderThreadTreeNode(int val) {
        this.val = val;
    }
}
public class E2TE {
    /*public static int i = 0;
    public static InOrderThreadTreeNode createTree(String str) {
        InOrderThreadTreeNode root = null;
        char ch = str.charAt(i);
        if(ch!='#') {
            root = new InOrderThreadTreeNode(Integer.valueOf(ch+""));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
            i++;
        }
        return root;
    }
    public static InOrderThreadTreeNode pre = null;
    public static InOrderThreadTreeNode inOrderThreadTree(InOrderThreadTreeNode root) {
        if (root == null) {
            return null;
        }
        inOrderThreadTree(root.left);
        if (root.left == null) {
            //设置前驱结点
            root.leftTag = 1;
            root.left = pre;
        }
        //如果结点的右子节点为NULL 处理前驱的右指针
        if (pre != null && pre.right == null) {
            //设置后继
            pre.rightTag = 1;
            pre.right = root;
        }
        //每处理一个节点 当前结点是下一个节点的前驱
        pre = root;
        //最后处理右子树
        inOrderThreadTree(root.right);
        return root;
    }*/
    public static List<InOrderThreadTreeNode> list = new ArrayList<>();
    public static InOrderThreadTreeNode findStartRoot(InOrderThreadTreeNode root) {
         if(root.leftTag==1 && root.left==null) {
             return root;
         }
         return findStartRoot(root.left);
    }
    public static void inOrderTraverse(InOrderThreadTreeNode root,StringBuilder stringBuilder) {
        if(root.rightTag==1 && root.right==null) {
            stringBuilder.append(root.val+" ");
            System.out.println(stringBuilder);
            return;
        }
        if(root.leftTag==0) {
            if(list.contains(root.left)) {
                stringBuilder.append(root.val+" ");
                list.add(root);
                inOrderTraverse(root.right,stringBuilder);
            }else {
                inOrderTraverse(root.left,stringBuilder);
                stringBuilder.append(root.val+" ");
                list.add(root);
            }
        }else {
            stringBuilder.append(root.val+" ");
            list.add(root);
            inOrderTraverse(root.right,stringBuilder);
        }
        return;
    }
    public static InOrderThreadTreeNode insert(InOrderThreadTreeNode xStartRoot
            ,InOrderThreadTreeNode p,InOrderThreadTreeNode x) {
        if(p.leftTag==1) {
            xStartRoot.left = p.left;
            x.right = p;
            p.left = x;
            p.leftTag = 0;
        }else {
            xStartRoot.left = p;
            x.right = p.right;
            p.right = x;
            p.rightTag = 0;
        }
        return p;
    }

    public static void main(String[] args) {
        InOrderThreadTreeNode p = null;
        InOrderThreadTreeNode x = null;
        InOrderThreadTreeNode pStartRoot = findStartRoot(p);
        InOrderThreadTreeNode xStartRoot = findStartRoot(x);
        inOrderTraverse(pStartRoot,new StringBuilder());
        inOrderTraverse(xStartRoot,new StringBuilder());
        InOrderThreadTreeNode root = insert(xStartRoot,p,x);
        inOrderTraverse(findStartRoot(root),new StringBuilder());
    }
}
